<!doctype html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  
  <meta name="generator" content="Hugo 0.98.0" />

  
  <meta name="description" content="走在通往幸福的路上">
  

  
  <link rel="apple-touch-icon" sizes="180x180" href="https://blog.v5u.win/apple-touch-icon.png">

  
  <link rel="icon" type="image/png" sizes="32x32" href="https://blog.v5u.win/favicon-32x32.png">

  
  <link rel="icon" type="image/png" sizes="16x16" href="https://blog.v5u.win/favicon-16x16.png">

  
  <link rel="manifest" href="https://blog.v5u.win/site.webmanifest">

  
  <link rel="mask-icon" href="https://blog.v5u.win/safari-pinned-tab.svg" color="">

  <meta name="msapplication-TileColor" content="">

  <meta name="theme-color" content="">

  
  <link rel="stylesheet" href="https://blog.v5u.win/css/bootstrap.min.css" />

  
  <title>epoll原理 | 为吾优</title>
  

  <style>
body {
  min-width: 300px;
}

.custom-navbar {
  margin-bottom: 1em;
  height: 60px;
}

.custom-navbar a {
  display: inline-block; 
  padding: 18px 0;
  margin-right: 1em; 
  font-weight: bold; 
}

.custom-navbar a:hover,
.custom-navbar a:focus {
  text-decoration: none; 
}

@media print {
  .custom-navbar {
    display: none;
  }
}

article {
  padding-bottom: 1em;
}

img {
  max-width: 100%;
}


body {
  background-color: #fff;
}



body {
  color: #212529;
}



a {
  color: #007bff;
}



a:hover,
a:focus {
  color: #0056b3;
}



.custom-navbar {
  background-color: #212529;
}



.custom-navbar a {
  color: rgba(255,255,255,.75);
}



.custom-navbar a:hover,
.custom-navbar a:focus {
  color: rgba(255,255,255,1);
}



.container {
  max-width: 800px;
}





</style>
</head>

<body>
  <nav class="custom-navbar">
  <div class="container">
    
    <a href="/">文章</a>
    
    <a href="/tags/">标签</a>
    
    <a href="/about/">关于</a>
    
    <a href="/index.xml">RSS</a>
    
  </div>
</nav>
  
  <div class="container">
    <article>
      <h1>epoll原理</h1>
<p>epoll原理</p>
<p>参考：https://my.oschina.net/editorial-story/blog/3052308</p>
<ol>
<li>网卡DMA传来数据，存入内存</li>
<li>网卡向CPU发送中断信号，操作系统得知有新数据到来，通过网卡中断程序去处理数据</li>
<li>将数据写入对应的socket接收缓冲区</li>
<li>唤醒对应进程</li>
<li>将进程放入工作队列</li>
</ol>
<h1 id="内核接收网络数据全过程"><strong>内核接收网络数据全过程</strong></h1>
<p>如下图所示，进程在 recv 阻塞期间，计算机收到了对端传送的数据（步骤①）——&gt;</p>
<p>数据经由网卡传送到内存（步骤②），——&gt;</p>
<p>然后网卡通过中断信号通知 CPU 有数据到达，CPU 执行中断程序（步骤③）。——&gt;</p>
<p>此处的中断程序主要有两项功能，先将网络数据写入到对应 socket 的接收缓冲区里面（步骤④），——&gt;</p>
<p>再唤醒进程 A（步骤⑤），——&gt;</p>
<p>重新将进程 A 放入工作队列中。</p>
<p>以上是内核接收数据全过程，这里我们可能会思考两个问题：</p>
<ul>
<li>其一，操作系统如何知道网络数据对应于哪个 socket？</li>
<li>其二，如何同时监视多个 socket 的数据？</li>
</ul>
<p>第一个问题：因为一个 socket 对应着一个端口号，而网络数据包中包含了 ip 和端口的信息，内核可以通过端口号找到对应的 socket。当然，为了提高处理速度，操作系统会维护端口号到 socket 的索引结构，以快速读取。</p>
<p>第二个问题是多路复用的重中之重，也正是本文后半部分的重点。</p>
<p><strong>select</strong> 简单的方法往往有缺点，主要是：</p>
<p>其一，每次调用 select 都需要将进程加入到所有监视 socket 的等待队列，每次唤醒都需要从每个队列中移除。这里涉及了两次遍历，而且每次都要将整个 fds 列表传递给内核，有一定的开销。正是因为遍历操作开销大，出于效率的考量，才会规定 select 的最大监视数量，默认只能监视 1024 个 socket。</p>
<p>其二，进程被唤醒后，程序并不知道哪些 socket 收到数据，还需要遍历一次。</p>
<p><strong>有没有减少遍历的方法？有没有保存就绪 socket 的方法？这两个问题便是 epoll 技术要解决的</strong>。</p>
<p>epoll 通过以下一些措施来改进效率：</p>
<p><strong>措施一：功能分离</strong></p>
<p>select 低效的原因之一是将“维护等待队列”和“阻塞进程”两个步骤合二为一。</p>
<p><strong>措施二：就绪列表</strong></p>
<p>select 低效的另一个原因在于程序不知道哪些 socket 收到数据，只能一个个遍历。如果内核维护一个“就绪列表”，引用收到数据的 socket，就能避免遍历。如下图所示，计算机共有三个 socket，收到数据的 sock2 和 sock3 被就绪列表 rdlist 所引用。当进程被唤醒后，只要获取 rdlist 的内容，就能够知道哪些 socket 收到数据。</p>
<h1 id="epoll-的原理与工作流程"><strong>epoll 的原理与工作流程</strong></h1>
<p><strong>创建 epoll 对象</strong></p>
<p><strong>维护监视列表</strong></p>
<p><strong>接收数据</strong></p>
<p><strong>阻塞和唤醒进程</strong></p>
<h1 id="epoll-的实现细节"><strong>epoll 的实现细节</strong></h1>
<p>相信读者对 epoll 的本质已经有一定的了解。但我们还需要知道 eventpoll 的数据结构是什么样子？</p>
<p>此外，就绪队列应该应使用什么数据结构？eventpoll 应使用什么数据结构来管理通过 epoll_ctl 添加或删除的 socket？</p>
<p>如下图所示，eventpoll 包含了 lock、mtx、wq（等待队列）与 rdlist 等成员，其中 rdlist 和 rbr 是我们所关心的。</p>
<p><strong>就绪列表的数据结构</strong></p>
<p>就绪列表引用着就绪的 socket，所以它应能够快速的插入数据。</p>
<p>程序可能随时调用 epoll_ctl 添加监视 socket，也可能随时删除。当删除时，若该 socket 已经存放在就绪列表中，它也应该被移除。所以就绪列表应是一种能够快速插入和删除的数据结构。</p>
<p>双向链表就是这样一种数据结构，epoll 使用双向链表来实现就绪队列（对应上图的 rdllist）。</p>
<p><strong>索引结构</strong></p>
<p>既然 epoll 将“维护监视队列”和“进程阻塞”分离，也意味着需要有个数据结构来保存监视的 socket，至少要方便地添加和移除，还要便于搜索，以避免重复添加。红黑树是一种自平衡二叉查找树，搜索、插入和删除时间复杂度都是O(log(N))，效率较好，epoll 使用了红黑树作为索引结构（对应上图的 rbr）。</p>
<p>注：因为操作系统要兼顾多种功能，以及由更多需要保存的数据，rdlist 并非直接引用 socket，而是通过 epitem 间接引用，红黑树的节点也是 epitem 对象。同样，文件系统也并非直接引用着 socket。为方便理解，本文中省略了一些间接结构。</p>

    </article>
  </div>

  
  
  

  
</body>

</html>